﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Tilver.ConsoleTest.Model
{

    /// <summary>
    /// 排序算法
    /// </summary>
    public class Sorter
    {
        #region  写一个函数，求两个整数之和，要求在函数体内不得使用+、-、* 、/四则运算符号。
        public int Add(int num1, int num2)
        {
            int sum, carry;
            do
            {
                sum = num1 ^ num2;
                carry = (num1 & num2) << 1;
                num1 = sum;
                num2 = carry;
            }
            while (num2 != 0);
            return num1;
        }
        #endregion

        #region 昌泡排序
        /* 冒泡排序
        比较相邻的元素。如果第一个比第二个大，就交换他们两个。
        对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
        针对所有的元素重复以上的步骤，除了最后一个。
        持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
         */
        public void BubbleSorter(int[] list)
        {
            int i, j, temp;
            for (i = list.Length; i > 0; i--)
            {
                for (j = 0; j < i - 1; j++)
                {
                    if (list[j] < list[j + 1])
                    {
                        temp = list[j];
                        list[j] = list[j + 1];
                        list[j + 1] = temp;
                    }
                }
            }
        }
        #endregion

        #region 选择排序


        /*选择排序
         首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找
         最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
         */
        public void SelectionSorter(int[] list)
        {
            int i, j, temp, min;
            for (i = 0; i < list.Length - 1; i++)
            {
                min = i;
                //查找最小值
                for (j = i + 1; j < list.Length; j++)
                {
                    if (list[min] > list[j])
                    {
                        min = j;
                    }
                }
                //最在值与序列末尾交换
                if (min != i)
                {
                    temp = list[min];
                    list[min] = list[i];
                    list[i] = temp;
                }
            }
        }
        #endregion

        #region 插入排序


        /*插入排序
         * 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
        从第一个元素开始，该元素可以认为已经被排序
        取出下一个元素，在已经排序的元素序列中从后向前扫描
        如果该元素（已排序）大于新元素，将该元素移到下一位置
        重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
        将新元素插入到该位置后
        重复步骤2~5
         */
        public void InsertSorter(int[] list)
        {
            for (int i = 1; i < list.Length; i++)
            {
                int temp = list[i];
                int j = i - 1;
                //与已排序的数比较，大于temp时，该数向后移
                while (j >= 0 && list[j] > temp)
                {
                    list[j + 1] = list[j];
                    j--;
                }
                //被排序数放到正确的位置
                list[j + 1] = temp;
            }
        }
        #endregion

        /// <summary>
        /// 1+2+3+4+....+n
        /// 1-2+3-4-5...n
        /// n!
        /// 1,1,2,3,5,8,13,21...第n位
        /// </summary>
        /// <returns></returns>
        public static int Func(int n)
        {
            #region 1+2+3+4+...+n

            //if (n <= 0) return 0;
            //return Func(n - 1) + n;

            #endregion

            #region 1-2+3-4+...+n

            if (n <= 0) return 0;
            return n % 2 == 0 ? Func(n - 1) - n : Func(n - 1) + n;

            #endregion

            #region n!

            //if (n == 0 || n == 1) return 1;
            //return n * Func(n - 1);

            #endregion

            #region 1,1,2,3,5,8,13,21...第30位

            //if (n <= 0) return 0;
            //if (n == 1 || n == 2) return 1;
            //return Func(n - 1) + Func(n - 2);

            #endregion

        }

        #region 随机生成和为S的N个整数
        /*
         * 投影法
         * 以生成和为20的4个数为例，可以先生成随机生成0到20之间的三个数字再排序，假设得到了4，7，18。
         * 然后在X-Y数轴上画出这三个数，然后将这些数值投影到Y轴上，得到Y轴上AB，BC，CD，DE这四段的长度和肯定为20
         */

        #endregion

    }
}
